Zakładamy, że rozpatrywane przez nas przestrzenie liniowe są przestrzeniami skończonego wymiaru nad ciałem liczb rzeczywistych. Każda przestrzeń $V$ wymiaru $n$ jest izomorficzna z przestrzenią $\mathbb R^n$, dlatego możemy utożsamić $V$ z $\mathbb R^n$.
Jeśli wprowadzić kartezjański układ współrzędnych $Oxy$ na płaszczyźnie, to każdy punkt $X$ płaszczyzny otrzyma etykietę w formie uporządkowanej pary liczb $(x,y)$. Para ta to współrzędne punktu $X$. Punkt o współrzędnych $(0,0)$ to $O$. Od $O$ do $X$ możemy poprowadzić wektor (strzałkę) $\overrightarrow{OX}$. Oczywiście wektor ma takie same współrzędne $x,y$ niekiedy zapisywane dla rozróżnienia w nawiasach kwadratowych: $[x,y]$. Strzałkę $\overrightarrow{OX}$ nazywamy wektorem wodzącym punktu $X$. Dalej, zarówno współrzędne strzałek jak i punktów zapisujemy w taki sam sposób w nawiasach okrągłych. Rozróżnienie między wektorami a punktami będziemy czynić w warstwie opisowej.
Jeśli $A$ i $B$ są dwoma punktami płaszczyzny oraz $A=(x_A,y_A)$, $B=(x_B,y_B)$, to wektorem o początku $A$ i końcu $B$ nazywamy wektor $\overrightarrow{AB}=(x_B-x_A, y_B-y_A)$. Jeśli punkt $C=(x_C, y_C)$ leży w odcinku o końcach $A$, $B$, to oczywiście musi istnieć liczba $t\in [0,1]$, że zachodzi równanie
$$ \overrightarrow{AC}= t\overrightarrow{AB}. $$
równoważnie: $$ (x_C-x_A, y_C-y_A)= t(x_B-x_A, y_B-y_A). $$ Stąd wyliczymy, że $$ (x_C, y_C)= (1-t)(x_A, y_A) +t(x_B,y_B). $$ Jeśli utożsamić punkt z jego wektorem wodzącym, to syntetycznie (bez współrzędnych) moglibyśmy ostatnie równanie zapisać tak:
$$ C=(1-t)A +tB. $$A jeszcze inaczej $$ C=\alpha A +\beta B, \tag{cc} $$ gdzie $\alpha, \beta\in [0,1]$ oraz $\alpha+\beta=1$ ($\beta$ to oczywiście $t$, zaś $\alpha$ to $1-t$).
Rozumiemy teraz, że $C$ leży w odcinku $[A,B]$ o końcach $A$, $B$ wtedy i tylko wtedy, gdy spełnia dla pewnych nieujemnych liczb $\alpha, \beta$, sumujących się do jedynki, równanie (cc). Podobne rozumowanie moglibyśmy przeprowadzić w $\mathbb R^3$ $-$ doszłaby jeszcze jedna współrzędna $-$ ale nie ma takiej potrzeby. Teraz pamiętając, że w zależności od kontekstu mówimy o punktach bądź wektorach, przyjmiemy następującą definicję.
Definicja 1. Niech $V $ $-$ przestrzeń liniowa nad $\mathbb R$ i niech $ u, v$ $-$ jej elementy. Odcinkiem w $V$ o końcach w punktach $u, v$ nazywamy zbiór
$$ [u, v] =\{(1-t)u + tv\colon t\in [0,1]\}=\{ \alpha u +\beta v\colon \alpha, \beta\in [0,1], \alpha +\beta=1\} $$Definicja 2. Podzbiór $K$ przestrzeni $V$ nazywamy wypukłym, jeśli dla wszelkich punktów $u,v$ leżących w $K$ odcinek $[u,v]$ jest zawarty w $K$. Symbolicznie, $$ \bigwedge_{u,v \in K}\,\, [u,v]\subseteq K. $$
Komentarz. Sama przestrzeń $V$ jest zbiorem wypukłym. Każdy zbiór jednoelementowy jest wypukły. Przyjmujemy także, że zbiór pusty jest wypukły. Można to wywnioskować z definicji. Jak?
Ćwiczenie 1. Do końców lekkiego i sztywnego patyka zamocowano ciężary o wadze $3$ kg w jednym z końców i $13$ kg w drugim. Gdzie należy podeprzeć patyk aby stworzyć układ w równowadze. (Porównaj z tak zwaną wagą rzymską.)
Definicja 3. Kombinacją wpukłą układu punktów $u^1, u^2, \ldots, u^m$ w $V$ nazywamy każdy element $u\in V$, który można przedstawić w postaci: $$ u=\alpha_1u^1+\alpha_2 u^2+\cdots + \alpha_mu^m, $$ gdzie wszystkie $\alpha_i, i=1,\ldots m$, nazywane współczynnikami kombinacji, są nieujemne i $\alpha_1+\alpha_2+\cdots+\alpha_m=1$.
(Ostrzeżenie. Symbol $u^k$ nie oznacza potęgi $u$. Jest to $k$-ty element układu punktów.)
Dowód. Rozumujemy przez indukcję. Oznaczmy przez $T_m$ twierdzenie głoszące, że kombinacja wypukła każdego układu co najwyżej $m$ punktów zbioru $K$ należy do $K$. Oczywiście twierdzenie $T_2$ jest prawdziwe na podstawie definicji zbioru wypukłego. Pozostaje więc wykazać, że dla wszelkich $m\ge 2$, $T_{m+1}$ jest konsekwencją $T_m$.
Niech $$ u=\alpha_1u^1+\cdots +\alpha_m u^m +\alpha_{m+1}u^{m+1} $$ oznacza kombinację wypukłą punktów $u^1, \ldots, u^{m+1}\in K$. Możemy przyjąć, że wszystkie $\alpha_k$ są dodatnie, gdyż w przeciwnym razie $u$ byłoby kombinacją wypukłą mniejszej liczby punktów należących do $K$ niż $m+1$. Takie $u$ leży w $K$ na podstawie założenia $T_m$. W szczególności $\alpha_{m+1}$ jest liczbą dodatnią, mniejszą niż $1$. Niech $\beta = \alpha_{m+1}$. Wtedy $1-\beta=\alpha_1+\cdots +\alpha_m$. I mamy $$ u= (1-\beta)\left( {{\alpha_1}\over{1-\beta}}u_1+\cdots + {{\alpha_m}\over{1-\beta}} u_m\right)+ \beta u^{m+1}. $$ Wyrażenie w nawiasie przedstawia punkt $v$, będący kombinacją wypukłą $m$ elementów zbioru $K$. Na podstawie przesłanki $T_m$, punkt ten leży w $K$. W takim razie $u$ leży w odcinku o końcach $v, u^{m+1}$ leżących w $K$. Na podstawie założenia o wypukłości $K$ wnosimy więc, że $u \in K$. $\square$
Przypomnienie. Rodziną zbiorów nazywamy zbiór, którego elementami są wyłącznie zbiory. Np. $\mathscr A =\{\{1,2,3\}, \{1,2,5\}, \{1,2,7\},\ldots \}$ jest rodziną zbiorów. Jej elementami są podzbiory zbioru liczb naturalnych $\{1,2,3\}$, $\{1,2, 5\}$, $\{1,2,7\}$ itd. Przekrój rodziny zbiorów składa się z tych i tylko tych elementów, które należą do każdego zbioru tej rodziny; tzn $$ x\in \bigcap \mathscr A \Leftrightarrow \bigwedge_{A\in\mathscr A} x\in A $$ W przypadku rozpatrywanego zbioru $\bigcap \mathscr A=\{1,2\}$.
Lemat 2. Przekrój każdej rodziny podzbiorów wypukłych przestrzeni liniowej $V$ jest sam zbiorem wypukłym.
Dowód. Niech $\mathscr B$ oznacza jakąkolwiek rodzinę zbiorów wypukłych. Wtedy jej przekrój $C=\bigcap \mathscr B$ jest zbiorem pustym bądź niepustym. Ponieważ zbiór pusty jest wypukły, pozostaje rozpatrzyć przypadek, gdy $C$ jest niepusty. Dla wszelkich elementów $x, y\in C$ i każdego $B\in \mathscr B$ mamy $x, y\in B$. Ponieważ $B$ jest wypukły, więc także $[x,y]\subseteq B$, dla każdego $B\in \mathscr B$. W konsekwencji, $[x,y]\subseteq C$. Wykazaliśmy więc, że $$ \bigwedge_{x,y\in C} [x,y]\subseteq C, $$ Na podstawie definicji 2, $C$ jest zbiorem wypukłym. $\square$
Definicja 4. Otoczką wypukłą podzbioru $A$ przestrzeni liniowej $V$ nazywamy część wspólną rodziny wszystkich podzbiorów wypukłych przestrzeni $V$ zawierających zbiór $A$.
Otoczkę wypukłą oznaczamy symbolem $\operatorname{conv} A$. Z pomocą symboliki mnogościowej możemy definicję otoczki wypukłej zapisać następująco:
Z naszej definicji wynika, że $A\subseteq \operatorname{conv} A$. W szczególności, jeśli $A$ nie jest zbiorem pustym, to nie jest też zbiorem pustym jego otoczka wypukła. Co więcej, z Lematu 2 wynika, że otoczka wypukła jest zbiorem wypukłym. Możemy zatem $\operatorname{conv} A$ scharakteryzować jako najmniejszy, w sensie zawierania, zbiór wypukły zawierający $A$.
Jeśli $B\subseteq V$ jest już zbiorem wypukłym, to oczywiście $\operatorname{conv} B=B$. Stąd dla wszelkich zbiorów $A\subseteq V$ zachodzi związek:
$$ \operatorname{conv} A=\operatorname{conv}(\operatorname{conv} A). \tag{idempotentość} $$Innymi słowy, otoczka wypukła zbioru $A$ składa się z kombinacji wypukłych układów punktów należących do zbioru $A$ i tylko z nich.
Dowód. Oznaczmy przez $A^*$ zbiór złożony ze wszystkich kombinacji wypukłych układów elementów leżących w $A$. Weźmy dowolne elementy $u, v\in A^*$ oraz dowolną liczbę $t\in [0,1]$. Z definicji $A^*$, $u$ jest kombinacją wypukłą pewnego układu $u^1,\ldots, u^m\in A$ i podobnie $v$ jest kombinacją wypukłą pewnego układu $v^1,\ldots, v^p\in A$. W takim razie,
$$ (1-t)u+tv= (1-t)(\alpha_1u^1+\cdots + \alpha_m u^m)+ t(\beta_1v^1+\cdots + \beta_pv^p), $$gdzie $\alpha_i,\, i=1,\ldots, m$ są współczynnikami kombinacji $u$, zaś $\beta_j,\, j=1,\ldots, p$ $-$ współczynnikami kombinacji $v$.
I dalej $$ (1-t)u+tv= (1-t)\alpha_1u^1+\cdots + (1-t)\alpha_m u^m + t\beta_1v^1+\cdots +t\beta_pv^p, $$ Co więcej, $$ (1-t)\alpha_1+\cdots + (1-t)\alpha_m+ t\beta_1+\cdots + t\beta_p= (1-t)(\alpha_1+\cdots + \alpha_m)+ t(\beta_1+\cdots + \beta_p)=(1-t)+t=1 $$
i wszystkie składniki w pierwszej z sum są nieujemne. Oznacza to, że punkt $(1-t)u+tv$ jest kombinacja wypukłą układu punktów $u^1,\ldots, u^m, v^1, \ldots, v^p$ leżących w $A$. Stąd musi on leżeć w $A^*$. Ponieważ tak być musi dla wszelkich liczb $t\in [0,1]$, więc $[u,v]\subseteq A^*$, dla wszelkich $u,v \in A^*$. Wykazaliśmy tym samym wypukłość $A^*$.
Ponieważ każdy $x\in A$ jest kombinacją wypukłą (jednoelementowego) układu elementów zbioru $A$: $x=1\cdot x$ , więc $A\subseteq A^*$. Jednak $\operatorname{conv} A$ jest najmniejszym zbiorem wypukłym zawierającym $A$, w takim razie
$$ \operatorname{conv} A\subseteq A^*. $$Z drugiej strony stąd, że $A\subseteq \operatorname{conv} A$ i ostatni zbiór jest wypukły wnosimy na podstawie twierdzenia 1, że
$$ A^*\subseteq \operatorname{conv} A, $$co ostatecznie kończy dowód. $\square$
Uwaga. Wyznaczanie otoczki wypukłej skończonego zbioru punktów rozmieszczonych na płaszczyźnie, albo w przestrzeni, albo ogólnie w $\mathbb R^n$ jest jednym z podstawowych i najważniejszych zadań geometrii obliczeniowej. Algorytmy tworzenia otoczki wypukłej są powszechnie wykorzystywane w oprogramowaniu służącym do projektowania wspomaganego komputerowo (CAD). Dostępne jest zarówno wysoce specjalistyczne oprogramowanie płatne (np. AutoCAD, Solid Edge, SolidWorks) jak i bezpłatne (np. Blender, OpenSCAD). Z programem OpenSCAD będziemy mieli do czynienia, dlatego zalecam, by już go sobie zainstalować i pobawić się. Jest bardzo prosty i naturalny w obsłudze. Obiekty trójwymiarowe tworzy się w nim przez pisanie programów. Język OpenSCAD-a ma bardzo prostą składnię.
Łącza do stron, na których można zobaczyć wyznaczanie otoczki wypukłej skończonego zbioru punktów płaszczyzny za pomocą algorytmu Grahama.
Definicja 5. Otoczkę wypukłą zbioru skończonego nazywamy wielowierzchołkiem lub wielościanem wypukłym ograniczonym.
Komentarze. Przypomnijmy, że jeśli $u,v\in V$ interpretować jako punkty, to $\overrightarrow{uv}$ jest wektorem równym $v-u$.
Zamiast mówić, że układ punktów $a^0, a^1, \ldots, a^m$ jest afinicznie niezależny, mówimy też, że punkty $a^0, a^1, \ldots, a^m$ są afinicznie niezależne.
Jeśli $V$ jest przestrzenią wymiaru $n$, np. $V=\mathbb R^n$, to liczba afinicznie niezależnych punktów w $V$ nie przekracza $n+1$
Jeśli płaszczyznę utożsamimy z $\mathbb R^2$, to, jak nietrudno się przekonać, punkty $A, B, C$ leżące na płaszczyźnie są afinicznie niezależne wtedy i tylko wtedy, gdy są wierzchołkami pewnego trójkąta.
Analogicznie, cztery afinicznie niezależne punkty w przestrzeni (to samo co $\mathbb R^3$) tworzą wierzchołki czworościanu. Natomiast na prostej (utożsamiamy z $\mathbb R$) możemy mieć co najwyżej dwa punkty afinicznie niezależne. Tworzą one końce pewnego odcinka.
Ćwiczenie 2. W oparciu o twierdzenie 3 wykazać, że dla każdych trzech afinicznie niezależnych punktów $A,B,C$ na płaszczyźnie $\mathbb R^2$, zbiór $\operatorname{conv}\{A,B,C\}$ jest trójkątem o wierzchołkach $A$, $B$, $C$.
Czy potrafilibyście w podobny sposób uzasadnić, że dla każdych czterech afinicznie niezależnych punktów $A, B, C, D$ w przestrzeni $\mathbb R^3$, $\operatorname{conv}\{A,B,C,D\}$ jest czworościanem o wierzchołkach $A$, $B$, $C$, $D$?
Definicja 7. Jeśli $a^0,a^1,\ldots, a^m$ są punktami afinicznie niezależnymi w przestrzeni liniowej $V$, to ich otoczkę wypukłą $\operatorname{conv} \{a^0,a^1,\ldots, a^m\}$ nazywamy $m$-wymiarowym sympleksem o wierzchołach $a^0,a^1,\ldots, a^m$.
Sympleks ten bywa oznaczany tak: $\sigma(a^0,a^1,\ldots, a^m)$.
Stwierdzenie 4. Układ punktów $a^0,a^1,\ldots,a^m$ jest afinicznie niezależny wtedy i tylko wtedy, gdy jedynym rozwiązaniem układu równań
o niewiadomych $\gamma_0, \gamma_1,\ldots, \gamma_m$ jest rozwiązanie zerowe $\gamma_0=\gamma_1=\ldots =\gamma_m=0$.
Ćwiczenie 3. Wykazać stwierdzenie 4. Wywnioskować z niego, że jeśli $x$ jest kombinacją wypukłą afinicznie niezależnego układu punktów $a^0,a^1,\ldots a^m$, to współczynniki kombinacji są określone jest jednoznacznie.
Twierdzenie 5. (Carathéodory) Niech $A$ oznacza podzbiór $n$-wymiarowej przestrzeni liniowej $V$. Punkt $x$ należy do $\operatorname{conv} A$ wtedy i tylko wtedy, gdy $x$ jest kombinacją wypukłą pewnego układu afinicznie niezależnych punktów leżących w $A$. W szczególności, jeśli $x\in\operatorname{conv} A$, to $x$ jest kombinacją wypukłą układu co najwyżej $n+1$ punktów leżących w $A$.
Dowód. Na podstawie twierdzenia 3 wystarczy wykazać, że każdy $x\in \operatorname{conv} A$ jest kombinacją wypukłą układu afinicznie niezależnych punktów leżących w $𝐴$. Wybierzmy najmniej liczny układ $a^0, a^1, \ldots a^m$ elementów zbioru $A$, że $x$ jest jego kombinacją wypukłą: $x=\alpha_0 a^0+\alpha_1a^1+\cdots +\alpha_m a^m$. Wszystkie $\alpha_i, i=0,\ldots, m $ muszą być dodatnie, bo w przeciwnym razie moglibyśmy odrzucić z układu taki element $a^j$, dla którego współczynnik $\alpha_j=0$, otrzymując układ mniej liczny. Przypuśćmy, że układ $a^0, a^1, \ldots a^m$ jest afinicznie zależny. Wtedy układ równań opisany w stwierdzeniu 4 musi mieć niezerowe rozwiązanie $\gamma_0, \gamma_1, \ldots, \gamma_m$. Ponieważ $\sum \gamma_i=0$, więc zbiór $I=\{i\colon \gamma_i<0\}$ jest niepusty. Niech $\tau= \min_{i\in I} \frac{\alpha_i}{-\gamma_i}$. Liczba $\tau$ jest dodatnia, więc
$$ \beta_i:=\alpha_i+\tau\gamma_i\ge 0, \quad \text{dla każdego $i=0,\ldots, m$} $$oraz dla pewnego wskaźnika $j\in I$, $\beta_j=0$. Stąd
\begin{align} x & = \alpha_0 a^0+\alpha_1a^1+\cdots +\alpha_m a^m +\tau(\gamma_0a^0+\gamma_1a^1+\cdots +\gamma_m a^m)\\ & = \beta_0a^0+\cdots+\beta_{j-1}a^{j-1}+\beta_{j+1}a^{j+1}+\cdots+\beta_ma^m, \end{align}gdzie $j$-ty wskaźnik został pominięty jako że $\beta_j=0$. Zauważmy jeszcze, że
$$ \sum \beta_i=\sum \alpha_i +\tau\sum \gamma_i = 1. $$W takim razie $x$ jest kombinacją wypukłą układu $a^0,\ldots, a^{j-1}, a^{j+1}, \ldots, a^m$, liczącego mniej elementów niż układ pierwotny, który jest najmniej liczny. Otrzymaliśmy sprzeczność dowodzącą, ze układ pierwotny $a^0, a^{1}, \ldots, a^m$ jest afinicznie niezależny.
Druga część twierdzenia jest konsekwencją faktu, że każdy układ afinicznie niezależny w przestrzeni liniowej wymiaru $n$ liczy co najwyżej $n+1$ elementów.$\square$
Ćwiczenie 4. Niech $X$ oznacza wewnętrzny punkt trójkąt $ABC$. Niech $A'$ oznacza punkt przecięcia prostych $AX$, $BC$ i podobnie $C'$ $-$ punkt przecięcia prostych $CX$, $AB$. Ponieważ $C'$ jest punktem wewnętrznym odcinka $[A,B]$, więc istnieje $r\in (0,1)$, że $C'=(1-r)A+rB$. Podobnie istnieje $s\in (0,1)$, że $A'=(1-s)B+sC$. Jak wiemy, $X$ jest kombinacją wypukłą punktów $A,B,C$. Wyrazić współczynniki tej kombinacji za pomocą $r, s$. Niech dodatkowo położenie $B'\in [C,A]$ będzie takie, jak na rysunku. Oczywiście $B'=(1-t)C+tA$, dla pewnej liczby $t\in (0,1)$. Wyrazić $t$ za pomocą $r$ i $s$.
Komentarz. Twierdzenie Carathéodory'ego można przefomułować tak. Otoczka wypukła podzbioru $n$-wymiarowej przestrzeni liniowej jest sumą mnogościową sympleksów o wierzchołkach w tym podzbiorze.
Ćwiczenie 5. Na wszystkich podzbiorach $n$ wymiarowej przestrzeni liniowej $V$ określmy operację $\operatorname{ls}$ w następujący sposób: $$ \operatorname{ls} A=\bigcup\{[a,b]\colon \{a,b\}\subseteq A\} $$ Innymi słowy, $x\in \operatorname{ls} A$ wtedy i tylko wtedy, gdy $x$ leży w pewnym odcinku o końcach w $A$.
Ćwiczenie 6.
Dano rodzinę $\mathscr J$ przedziałów domkniętych osi liczbowej $\mathbb R$. Wykazać, że jeśli każda para tych przedziałów ma niepusty przekrój, to wszystkie mają niepusty przekrój.
Kostką standardową w $\mathbb R^n$ nazywamy każdy zbiór $K\subseteq\mathbb R^n$ postaci $$ K=[a_1,b_1]\times\cdots\times[a_n,b_n],\quad \text{gdzie $a_i\le b_i$, $i=1,\ldots, n$} $$ Dano rodzinę $\mathscr K$ takich kostek. Czy prawdą jest, że jeśli każda para kostek tej rodziny ma niepusty przekrój, to przekrój wszytkich kostek jest niepusty. (Zadanie domowe. Zapisać rozwiązanie.)
Kostka standardowa w $\mathbb R^2$ to prostokąt o bokach równoległych do osi układu współrzędnych. Dwa takie prostokąty nazywamy prawie przyległymi, jeśli istnieje prosta równoległa do jednej z osi układu, że prostokąty leżą po przeciwnych stronach tej prostej i nadto oba mają boki zawarte w tej prostej. Ile co najwyżej elementów może liczyć rodzina kostek o tej właśności, że każde dwa prostokąty tej rodziny są prawie przyległe?
Ćwiczenie 7. Udowodnić, że przekrój dwu wielowierzchołków sam jest wielowierzchołkiem. (Za rozwiązanie stopień o jeden w górę.)
Definicja 8. Podzbiór $A$ przestrzeni liniowej $V$ jest afinicznie zależny, jeśli zawiera układ $a^0,a^1, \ldots, a^m$, który nie jest afinicznie niezależny.
Lemat 6. (Radon) Jeśli podzbiór $A$ przestrzeni liniowej $V$ jest afinicznie zależny, to można $A$ rozłożyć na dwa rozłączne podzbiory $B$, $C$, że $\operatorname{conv}(B)\cap \operatorname{conv}(C)\neq \emptyset$.
Dowód. Wybierzmy w $A$, układ $a^0,a^1, \ldots, a^m$, który jest afinicznie zależny. Na mocy stwierdzenia 4 istnieją skalary $\gamma_i$ nie wszystkie równe $0$, które spełniają układ równań opisany w stwierdzeniu 4. Ponieważ suma wszystkich $\gamma_i$ jest zero, więc pośród nich są zarówno liczby dodatnie jak i ujemne. Utwórzmy dwa zbiory $$
I^-=\{i\in \{0,\ldots m\}\colon \gamma_i<0\},\quad I^+=\{i\in \{0,\ldots m\}\colon \gamma_i\geq 0\}.
$$
Ponieważ zbiory te są rozłączne i w sumie dają $\{0,\ldots m\}$, więc z drugiego z równań występujących w stwierdzeniu 4
$$
\sum_{i\in I^+} \gamma_i a^i= \sum_{i\in I^-} (-\gamma_i)a^i
$$
Określmy $\tau=\sum_{i \in I^+} \gamma_i$. Z pierwszego z równań, $\tau= \sum_{i \in I^-} (-\gamma_i)$. Oczywiście $\tau$ jest liczba dodatnią i nadto
$$
\sum_{i\in I^+} \frac{\gamma_i}\tau a^i= \sum_{i\in I^-} \frac{-\gamma_i}\tau a^i. \tag{c}
$$
Przy czym prawa strona jest kombinacją wypukłą elementów zbioru $B:=\{a^i\colon i \in I^-\}$, zaś lewa przedstawia kombinację wypukłą pewnych elementów zbioru $C:=A\setminus B$
Jednak obie strony przedstawiają ten sam element, nazwijmy go $x$. W takim razie,
$$
x\in \operatorname{conv} B\cap \operatorname{conv} C.
$$
$\square$
Twierdzenie 7. (Helly) Niech $\mathscr C=\{C_1,C_2,\ldots, C_m\}$ oznacza skończoną rodzinę podzbiorów wypukłych $n$-wymiarowej przestrzeni liniowej $V$. Niech $m > n+1$. Jeśli każda $(n+1)$-elementowa podrodzina rodziny $\mathscr C$ ma niepusty przekrój, to także rodzina $\mathscr C$ ma niepusty przekrój.
Dowód Radona. Jeśli przekrój rodziny $\mathscr C$ jest pusty, to wybierzmy najmniej liczną podrodzinę $\mathscr D=\{D_1,\ldots D_p\}$ rodziny $\mathscr C$, która także ma pusty przekrój. Wtedy
Oczywiście $p>n+1$, bo każda $(n+1)$-elementowa podrodzina ma niepusty przekrój. Utwórzmy zbiory $$ E_i=\bigcap_{k: k\neq i} D_k, \quad i=1,\ldots p. $$ Są one niepuste na mocy definicji $\mathscr D$. W każdym z $E_i$ wybierzmy element $x_i$ i utwórzmy zbiór $A=\{x_i\colon i=1,\ldots, p\}$. Dla każdej pary $i<j$, elementy $x_i$, $x_j$ są różne, w przeciwnym razie $E_i\cap E_j\neq \emptyset$. Jednak $E_i\cap E_j=\bigcap_k D_k=\bigcap \mathscr D$. W rezultacie $\bigcap \mathscr D\neq \emptyset$ co przeczyłoby definicji $\mathscr D$. Stąd $A$ liczy dokładnie $p$ elementów. Ponieważ $p>n+1$, więc na mocy lematu Radona możemy $A$ rozbić na dwa rozłączne podzbiory $B$ i $C$ których otoczki wypukłe kroją się niepusto, więc należy do nich pewien element $u$. Dla uproszczenia przyjmijmy, że $B=\{x_1, \ldots, x_k\}$, zaś $C=\{x_{k+1}, \ldots, x_{p}\}$. Oczywiście, zbiory $B$ i $C$ nie muszą składać się z punktów ponumerowanych kolejnymi liczbami, ale rozumowanie w przypadku ogólnym przebiega w taki sam sposób. Zauważmy teraz, że w zgodzie z definicją punktów $x_i$ mamy
Jednak prawe strony są zbiorami wypukłymi, więc na mocy definicji otoczki wypukłej mamy także $$ \operatorname{conv} B\subseteq D_{k+1}\cap\cdots\cap D_{p}, \quad \operatorname{conv} C\subseteq D_1\cap\cdots\cap D_k. $$ Wtedy $u$ należąc zarówno do $\operatorname{conv} B$ jak i $\operatorname{conv} C$, musi należeć do części wspólnej zbiorów $D_{k+1}\cap\cdots\cap D_{p}$ i $D_1\cap\cdots\cap D_k$, ta jest jednak równa $\bigcap \mathscr D$. I otrzymalismy sprzeczność z założeniem, że $\mathscr D$ ma pusty przekrój. $\square$
Uwagi. (1) Pierwotny dowód twiedzenia przeprowadzony przez samego Helly'ego wyglądał inaczej. W czasie pierwszej wojny światowej Helly i Radon trafili do niewoli rosyjskiej. Tam spotkali się i Helly opowiedział Radonowi o swoim twierdzeniu. Potem Radon został wypuszczony, powrócił do Wiednia, i opublikował swój dowód (1921). Helly ciągle pozostawał w niewoli i jego dowód ujrzał światło dzienne w 1923 roku. Na ćwiczeniach przeprowadzimy rozumowanie Helly'ego przynajmniej dla przypadku dwuwymiarowego (pierwszy krok indukcyjny).
(2) Twierdzenie Helly'ego można uogólnić na nieskończone rodziny zbiorów wypukłych. Wtedy jednak potrzebujemy dodatkowych założeń natury topologicznej. Ograniczymy się do przestrzeni $\mathbb R^n$. Przypomnijmy, że odległość euklidesową dwóch punktów $x, y\in \mathbb R^n$ określamy wzorem:
$$ d(x,y)=\sqrt{(x_1-y_1)^2+(x_2-y_2)^2+\cdots +(x_n-y_n)^2}. \tag{ed} $$Kulą domkniętą o środku $x$ i promieniu $r$ nazywamy zbiór $B(x,r)=\{y\colon d(x,y)\leq r\}$
Kulą otwartą o środku $x$ i promieniu $r$ nazywamy zbiór $ U(x,r)=\{y\colon d(x,y)< r\}$
Podzbiór $W\subseteq \mathbb R^n$ nazywamy otwartym, jeśli dla każdego $x\in W$ istnieje $r>0$, że $U(x,r)\subseteq W.$
Podzbiór $D\subseteq \mathbb R^n$ jest domknięty, jeśli jego dopełnienie $\mathbb R^n\setminus D$ jest zbiorem otwartym.
Podzbiór $K\subseteq \mathbb R^n$ jest ograniczony, jeśli jest zawarty w pewnej kuli.
Rodzinę $\mathscr D$ zbiorów nazwiemy scentrowaną, jeśli każda jej skończona podrodzina ma niepusty przekrój.
Można udowodnić, że jeśli $\mathscr D$ jest rodziną scentrowaną podzbiorów domkniętych przestrzeni $\mathbb R^n$ i przynajmniej jeden z tych podzbiorów jest ograniczony, to część wspólna zbiorów rodziny $\mathscr D$ jest niepusta. Łącząc ten fakt z twierdzeniem Helly'ego otrzymamy
Twierdzenie 8. (Helly) Niech $\mathscr D$ oznacza rodzinę podzbiorów wypukłych i domkniętych przestrzeni $\mathbb R^n$ i niech przynajmniej jeden element tej rodziny będzie zbiorem ograniczonym. Jeśli każda podrodzina rodziny $\mathscr D$ licząca co najwyżej $n+1$ elementów ma niepusty przekrój, to i sama $\mathscr D$ ma niepusty przekrój.
Twierdzenie Helly'ego oraz liczne jego uogólnienia i zastosowania stanowią ciągle przedmiot żywego zainteresowania. (zob. tutaj)
Zadanie Steinhausa o podziale tortu
Paweł i Gaweł mają podzielić się trójkątnym tortem. Gaweł zastrzegł sobie, że odetnie prostolinijnym cięciem swoją część. Paweł zgodził się na to pod warunkiem, że on wyznaczy przedtem punkt $P$, przez który musi przejść Gawłowe cięcie. Ponieważ tort ma jednakową grubość w każdym miejscu i jest także jednorodny co do smaku, więc zadanie sprowadza się do geometrii płaskiej. Pytanie brzmi: jak ma Paweł wyznaczyć punkt $P$, żeby najlepiej obronić sie przed łakomstwem Gawła? Drugie pytanie: jak wielka nadwyżka przypadnie Gawłowi, jeżeli Paweł rozwiąże pierwsze zadanie trafnie, a Gaweł potem odetnie możliwie największą część tortu?
Gdyby kształt tortu zależał od Pawła, to mógłby on wybrać figurę mającą środek (a więc koło, kwadrat, elipsę itd.) i umieścić $P$ w tym środku. Tym sposobem przywilej Gawła straciłby znaczenie. Ale ciekawe jest pytanie, jaki kształt tortu jest (przy zachowaniu warunków podziału wypowiedzianych na początku) najlepszy dla Gawła i jaką największą nadwyżkę może sobie zapewnić Gaweł przez trafny wybór kształtu?
Źródło: Hugo Steinhaus, Sto zadań, Wydawnictwo PHU "DIP", Warszawa 1993 (istnieją inne wydania tej książki).
Komentarz: Ogólnej odpowiedzi udzielił Branko Grünbaum w pracy:
$-$, Partitions of mass-distributions and of convex bodies by hyperplanes, Pacific Journal of Mathematics, 10 (1960), 1257$-$1261.
W pracy tej rozpatrywany jest też przypadek ogólniejszego zadania:
Zadanie Płaski tort został podzielony, a jego kawałki rozsunięte po całym stole. Paweł wybiera punkt, a Gaweł zabiera tyle tortu, ile może oddzielić prostolinijnym cięciem przechodzącym przez obrany punkt. Wykazać, że Paweł poprawnym wyborem punktu może sobie zapewnić $\frac 1 3 $ tortu.
Rozwiązanie. Wykorzystamy twierdzenie Hellyeg'o. Niech $T$ oznacza płaską figurę przedstawiającą kawałki tortu. Rozpatrzmy wszystkie takie domknięte półpłaszczyzny $\Gamma$, że $|T\cap \Gamma|> \frac 2 3 |T|$. Niech $\mathscr G$ oznacza rodzinę tych półpłaszczyzn wzbogaconą dodatkowo o jakiekolwiek koło domknięte zawierające wszystkie kawałki tortu.
Wykażmy, że każde trzy elementy $K_1, K_2,K_3$ rodziny $\mathscr G$ kroją się niepusto. Z prawa de Morgana
$$ |T\setminus (K_1\cap K_2\cap K_3)|= |(T\setminus K_1)\cup (T\setminus K_2)\cup (T\setminus K_3)|\le \sum_{i=1}^3 |T\setminus K_i|. $$Jednak $|T\setminus K_i|<\frac 1 3|T|$, zatem $|T\setminus (K_1\cap K_2\cap K_3|< |T|$. Co dowodzi, że $K_1\cap K_2\cap K_3$ jest zbiorem niepustym.
Rodzina $\mathscr G$ spełnia założenia twierdzenia 8, więc ma niepusty przekrój. Niech punkt $P$ należy do tego przekroju i niech $\ell$ będzie prostą przechodzącą przez $P$. Prosta ta jest wspólnym brzegiem dwóch dopełniczych półpłaszczyzny domkniętych $\Pi_\ell^-$, $\Pi_\ell^+$.
Zauważmy, że każda z części $T\cap\Pi_\ell^-$ jak i $T\cap\Pi_\ell^+$ stanowi co najmniej jedną trzecią tortu, bo gdyby np. $|T\cap\Pi_\ell^-|< \frac 1 3 |T|$, to wtedy $|T\cap\Pi_\ell^+|> \frac 2 3 |T|$, Niech $n$ oznacza jednostkowy wektor prostopadły do $\ell$ skierowany do wewnątrz półprzestrzeni $\Pi_\ell^+$. Przesuńmy tę półprzestrzeń o wektor $\varepsilon n$, gdzie $\varepsilon >0$. Oznaczmy otrzymaną w ten sposób półprzestrzeń przez $\Omega$. Jeśli liczba $\varepsilon$ jest dostatecznie bliska $0$, to nadal będzie zachodziła nierówność $|T\cap \Omega |>\frac 2 3 |T|$, to znaczy, $\Omega \in \mathscr G$. Jednocześnie $P\not\in \Omega$, co przeczy określeniu punktu $P$.
Lazurowe figury stanowią kawałki toru. Ciemniejszą barwą zaznaczono półpłaszczyznę $\Omega$ powstałą przez dostatecznie małe przesunięcie półpłaszczyzny $\Pi\ell^+$ w kierunku wektora $n$._
Definicja 8. Niech $A$ będzie niepustym podzbiorem ograniczonym przestrzeni $\mathbb R^n$. Średnicą zbioru $A$ nazywamy wielkość
$$ \operatorname{diam}A=\sup \{d(x,y)\colon x, y\in A\}, $$gdzie $d(x,y)$ oznacza odległość euklidesową określoną wzorem (ed). Promieniem zbioru $A$ nazywamy liczbę $\operatorname{rad} A$ równą kresowi dolnemu promieni kul domkniętych zawierających $A$.
Przypomnienie. W przestrzeni $\mathbb R^ n$ określamy (standardowy) iloczyn skalarny wektorów $x$, $y$ wzorem:
$$ \langle x, y\rangle =x_1y_1+x_2y_2+\cdots +x_ny_n. $$Wielkość
$$ \|x\|= \sqrt{x_1^2+x_2^2+\cdots +x_n^2} =\sqrt{\langle x, x\rangle} $$nazywamy normą wektora $x$.
Zachodzi nierówność Schwarza
$$ |\langle x, y\rangle|\le \|x\|\|y\|. $$Przypadek równości ma miejsce jedynie wówczas, gdy wektory $x$ i $y$ są współliniowe.
Między normą a odległością euklidesową zachodzi następujący związek:
$$ d(x,y)=\|x-y\|=\|y-x\|. $$Odległość $d$ ma następujące własności:
dla wszelkich $x,y,z\in \mathbb R^n$.
Nierówność trójkąta wynika z nierówności Schwarza.
Twierdzenie 9. (Jung) Jeśli $A$ jest ograniczonym podzbiorem przestrzenie $\mathbb R^n$, to
$$ \operatorname{rad} A \le \operatorname{diam} (A) \sqrt{\frac n {2(n+1)}}. $$Dowód twierdzenia Junga odkładamy na później.
Zagadnienie Borsuka. W pracy z roku 1937, wybitny polski geometra Karol Borsuk (1905$-$1982) postawił następujące pytanie:
Czy prawdą jest, że każdy podzbiór ograniczony $A$ przestrzeni $\mathbb R^n$ można nakryć $n+1$ zbiorami o średnicach mniejszych niż $\operatorname{diam} A$?
Pytanie to upowszechniło się pod nazwą hipotezy Borsuka, a więc przypuszczenia, że takie nakrycie rzeczywiście istnieje. Sam Borsuk dowiódł, że dla $n=2$ jego pytanie ma odpowiedź twierdzącą. Julian Perkal i E. H. Eggleston udowodnili, że odpowiedź jest twierdząca także w przypadku $n=3$. Dowody polegały na 'opakowaniu' $A$ w zbiór o prostej strukturze geometrycznej i średnicy nieco większej niż $\operatorname{diam A}$, i wykazaniu, że zbiór opakowujący można pokryć zbiorami o średnicy mniejszej od średnicy zbioru $A$. W przypadku płaskim opakowaniem jest odpowiednio dobrany sześciokąt foremny (można by użyć kwadratu z odpowiednio ściętymi wierzchołkami), a w przypadku trójwymiarowym ośmiościan foremny z odpowiednio ściętymi wierzchołkami. Nie wiemy jak jest nawet w przypadku $n=4$. Dla tego przypadku Marek Lassak skonstruował opakowanie dające pokrycie liczące 9 zbiorów w miejsce oczekiwanych 5 i jest to najlepszy do tej pory rezultat. W 1991 izraelscy matematycy Jeff Kahn and Gil Kalai wykazali, że w przestrzeniach wymiarów $n>2014$ istnieją kontrprzykłady. Więcej na ten temat można znaleźć w wikipedii